package syf.search;

public class InsertSearch {
    public static void main(String[] args) {
        int[] arr=new int[100];
        for (int i=0;i<arr.length;i++ ) {
            arr[i] = i;
        }
        int i= insertSearch(arr,0,arr.length-1,10);
        System.out.println(i);
    }

    /**
     * 插值查找算法
     * @param arr 待排序的数组
     * @param left 最左索引
     * @param right 最右索引
     * @param val 待查找的值
     * @return 待查找值在数组中下标，没有则为-1
     */
    public static int  insertSearch(int[] arr,int left,int right,int val){
        System.out.println("====");
        //如果待查找的值大于最大值和小于最小值，肯定找不到直接返回-1
        if (arr[0]>val||arr[right]<val)
            return -1;
        //插入查找的自适应中间值下标
        int mid=left+(right-left)*(val-left)/(arr[right]-arr[left]);
        //如果待查找的值小于中间值，从左边找
        if (val<arr[mid]){
            return insertSearch(arr,left,mid-1,val);
        }else if (val>arr[mid]){//如果待查找的值大于中间值，从右边找
            return insertSearch(arr,mid+1,right,val);
        }else {//已经找到，返回中间值下标
            return mid;
        }
    }
}
